
	
GeneticAlgorithm::GeneticAlgorithm( const char* input_file ) : Algorithm( input_file ) {
	//number of individuals
	n = 100;
	quality_best = 0;
	population = new int*[n];
}

GeneticAlgorithm::~GeneticAlgorithm() {
	deletePopulation(population);
}

int* GeneticAlgorithm::randomInit() {
	int index[L];
	for( int i = 0; i < L; ++i )
		index[i] = i;
	
	for( int i = 0; i < L; ++i )
		swap( &index[i], &index[rand()%L] );
	
	int *init_solution = new int[k];
	for( int i = 0; i < k; ++i )
		init_solution[i] = index[i];
		
	return init_solution;
}

void GeneticAlgorithm::solve() {
	
	int fitness[n];
	
	for(int i = 0; i < n; ++i)
		population[i] = randomInit();
	
	time_t start = time(NULL);
	do{
		for(int i = 0; i < n; ++i)
			fitness[i] = assessFitness(population[i]);
		
		for( int i = 0; i < n; i = i+2) {
			int i1 = rouletteSeletion(population, fitness);
			int i2 = rouletteSeletion(population, fitness);
			
			crossover(population[i1], population[i2]);
			
			mutate(population[i1]);
			mutate(population[i2]);
			
			VNS(population[i1]);
			VNS(population[i2]);
		}
		
	}while((time(NULL) - start < 60));
	
}

int GeneticAlgorithm::rouletteSeletion(int** pop, int* fit) {
	
	int sum_fit = 0;
	for(int i = 0; i < n; ++i)
		sum_fit += fit[i];
		
	float probabilities[n];
	probabilities[0] = (float)fit[0]/(float)sum_fit;
	for(int i = 1; i < n; ++i)
		probabilities[i] = 
			(float)fit[i]/(float)sum_fit + probabilities[i-1];
	probabilities[n-1] = 1;
	
	float prob = (float)rand()/(float)RAND_MAX;
	for(int i = 0; i < n; ++i)
		if(prob <= probabilities[i])
			return i;
}

void GeneticAlgorithm::crossover(int* individual1, int* individual2) {
	
	bool intersection[2*L+1];
	memset(intersection,false,(2*L+1)*sizeof(bool));
	
	for( int i = 0; i < k; ++i )
		for( int j = 0; j < k; ++j )
			if(individual1[i] == individual2[j]){
				intersection[individual1[i]] = true;
				break;
			}

	for(int i = 0; i < k; ++i) {
		if( intersection[individual1[i]] || intersection[individual2[i]])
			continue;
		float p = (float)rand()/(float)RAND_MAX;
		if(p <= 0.5)
			swap(&individual1[i],&individual2[i]);
	}
}

int* GeneticAlgorithm::mutate(int* individual) {
	
	bool used_sets[L];
	memset( used_sets, false, L*sizeof(bool) );
	for (int i = 0; i < k; ++i) 
		used_sets[individual[i]] = true;
	
	float p = 1.0/(float)k;
	for (int i = 0; i < k; ++i) {
		float r = (float)rand()/(float)RAND_MAX;
		if (r <= p) {
			
			int temp = individual[i];
			
			individual[i] = pickOneSet(used_sets);
			
			used_sets[individual[i]] = true;
			used_sets[temp] = false;
			
		}
	}
	return individual;
}

int GeneticAlgorithm::pickOneSet(bool* used_sets){
	int index[L];
	for (int i = 0; i < L; ++i) 
		index[i] = i;
	
	for (int i = 0; i < L; ++i) 
		swap(&index[i], &index[rand()%L]);
	
	for (int i = 0; i < L; ++i)
		if(!used_sets[index[i]])
			return index[i];
	
	cout << "pickOneSet - Erro: nao foi achado um conjunto nao usado" << endl;
	exit(-1);
}

void GeneticAlgorithm::deletePopulation(int** p) {
	for(int i = 0; i < n; ++i)
		delete [] population[i];
	delete [] population;
}

void GeneticAlgorithm::VNS(int* S) {
	int* ret = new int[k];
	copySolution(ret,S);
	int quality_ret = assessFitness(ret);
	
	for(int i = 1; i <= k; ++i ) {
		int* new_solution = changeN(S, i);
		
		int quality_new_solution = assessFitness(new_solution);
		
		if(quality_new_solution > quality_ret) {
			copySolution(ret,new_solution);
			quality_ret = quality_new_solution;
			i = 0;
		}
		delete [] new_solution;
	}
	copySolution(S,ret);
	delete [] ret;
}

int* GeneticAlgorithm::changeN(int* S, int n) {
	
	int is_in_solution[L];
	memset(is_in_solution,0,L*sizeof(int));
	
	for( int i = 0; i < k; ++i )
		is_in_solution[S[i]] = 1;
	
	int* new_solution = new int[k];
	
	int changes[k];
	for(int i = 0; i < k; ++i) {
		changes[i] = i;
		new_solution[i] = S[i];
	}
	
	for(int i = 0; i < k; ++i)
		swap(&changes[i], &changes[rand()%k]);
	
	int set_to_be_inserted;
	for(int i = 0; i < n; ++i) {
		int set_to_be_inserted;
		
		int sets_to_be_inserted[L];
		for(int l = 0; l < L; ++l)
			sets_to_be_inserted[l] = l;
		
		for(int l = 0; l < L; ++l)
			swap(&sets_to_be_inserted[l], &sets_to_be_inserted[rand()%L]);
		
		for(int l = 0; l < L; ++l) {
			if(!is_in_solution[sets_to_be_inserted[l]]) {
				set_to_be_inserted = sets_to_be_inserted[l];
				break;
			}
		}

		is_in_solution[new_solution[changes[i]]] = 0;
		new_solution[changes[i]] = set_to_be_inserted;
		is_in_solution[new_solution[changes[i]]] = 1;
	}
	
	return new_solution;
}

int GeneticAlgorithm::assessFitness(int* s) {
	Set temp;
	temp.union_(&sets[s[0]]);
	
	for( int i = 1; i < k; ++i )
		temp.intersection(&sets[s[i]]);

	if(temp.cardinality() > quality_best)
		quality_best = temp.cardinality();
	
	return temp.cardinality();
}

void GeneticAlgorithm::copySolution(int* s1, int* s2) {
	for( int i = 0; i < k; ++i )
		s1[i] = s2[i];
}

int GeneticAlgorithm::getQualityOfBest() {
	return quality_best;
}
